package test.skiplist;

import java.util.Random;

public class SkipList {

    final int HEAD_VALUE = -1;  // 链表头节点的值
    Node head;

    int level;

    public SkipList() {
        head = new Node(HEAD_VALUE, null, null);
        level = 1;
    }

    public boolean search(int target) {
        Node result = head;
        while (result != null ) {
            while (result != null && result.value <= target) {
                result = result.next;
            }
            if (result != null && result.value == target) {
                return true;
            }
            result = result.down;
        }
        return false;
    }

    public void add(int num) {
        Node prev = head;
        Node[] nodes = new Node[level];
        int i = 0;
        while (prev != null ) {
            while (prev.next != null && prev.next.value < num) {
                prev = prev.next;
            }
            nodes[i++] = prev;
            prev = prev.down;
        }
        Node newNode = new Node(num, null, prev.next);
        nodes[--i].next = newNode;

        //抛硬币
        addIndicesByCoinFlip(newNode, nodes);
    }

    private void addIndicesByCoinFlip(Node node, Node[] nodes) {

        int i = nodes.length - 2;
        while (i >= 0) {
            int random = new Random().nextInt(2);
            if (random == 0) {
                break;
            }
            Node newNode = new Node(node.value, nodes[i + 1].next, nodes[i].next);
            nodes[i].next = newNode;
            i--;
        }
        if (i > 0) {
            return;
        }
        int random = new Random().nextInt(2);
        if (random == 0) {
            return;
        }

        Node newNode = new Node(node.value, nodes[0].next, null);
        Node levelHead = new Node(head.value, head, newNode);
        level++;
        head = levelHead;
    }

    public boolean erase(int num) {
        Node prev = head;

        while (prev != null ) {
            while (prev.next != null && prev.next.value < num) {
                prev = prev.next;
            }
            if (prev.next != null && prev.next.value == num) {
                break;
            }
            prev = prev.down;
        }
        if (prev.next == null || prev.next.value != num) {
            return false;
        }
        while (prev != null) {
            Node next = prev.next;
            prev.next = next.next;
            next.next = null;
            next.down = null;
            prev = prev.down;
        }

        return true;
    }

    class Node {
        int value;
        Node down;
        Node next;

        public Node() {

        }

        public Node(int value, Node down, Node next) {
            this.value = value;
            this.down = down;
            this.next = next;
        }

    }
}
